package cn.zifangsky.sort;

/**
 * 堆排序
 *
 * @author zifangsky
 * @date 2019/1/4
 * @since 1.0.0
 */
public class HeapSort {

    /**
     * 堆排序
     * <p><b>时间复杂度：</b>O(NlogN)</p>
     * @author zifangsky
     * @date 2019/1/4 16:27
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sort(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;

        //1. 构建最大堆
        buildHeap(array);

        //2. 依次删除
        for(int i = length; i > 0; i--){
            //2.1 不断删除根节点
            int temp = deleteMax(array, i);
            //2.2 将删除的这个节点放到末尾
            array[i - 1] = temp;
        }

        //3. 返回排序好的数组
        return array;
    }

    /**
     * 将无序数组建立成二叉堆
     */
    private static void buildHeap(int[] array){
        //遍历数组，平衡节点位置
        for(int i = (array.length - 1); i >= 0; i--){
            //下浮调整
            downAdjust(array, array.length, i);
        }
    }

    /**
     * 删除根节点
     * <p>思路：将最后一个节点移到根节点，然后将当前根节点不断下浮到适当位置，最后将最后一个节点置空并返回原来的根节点</p>
     */
    private static int deleteMax(int[] array, int size){
        //标记一下原来的根节点
        int root = array[0];

        //1. 将最后一个节点移到根节点
        array[0] = array[size - 1];

        //2. 将当前根节点不断下浮到适当位置
        downAdjust(array, size, 0);

        //返回删除的根节点
        return root;
    }

    /**
     * 下浮调整
     * @param point 待调整的节点坐标
     */
    private static void downAdjust(int[] array, int size, int point){
        //左孩子节点的索引
        int leftChildIndex = point * 2 + 1;
        //右孩子节点的索引
        int rightChildIndex = point * 2 + 2;

        //让所有不满足条件的非叶子节点依次下沉
        while ((leftChildIndex < size && array[point] < array[leftChildIndex])
                || (rightChildIndex < size && array[point] < array[rightChildIndex])){
            //只有左孩子节点或者左孩子节点大于右孩子节点，当前节点跟左孩子节点交换
            if(rightChildIndex >= size || array[leftChildIndex] >= array[rightChildIndex]){
                int temp = array[leftChildIndex];
                array[leftChildIndex] = array[point];
                array[point] = temp;

                point = leftChildIndex;
            }
            //左孩子节点小于右孩子节点，当前节点跟右孩子节点交换
            else if(array[leftChildIndex] < array[rightChildIndex]){
                int temp = array[rightChildIndex];
                array[rightChildIndex] = array[point];
                array[point] = temp;

                point = rightChildIndex;
            }

            leftChildIndex = point * 2 + 1;
            rightChildIndex = point * 2 + 2;
        }
    }

}
